//class Solution {
//public:
//    bool canJump(vector<int>& nums)
//    {
//        int len = nums.size();
//
//        if (len == 1)
//        {
//            return true;
//        }
//
//        for (int i = 0; i < len; i++)
//        {
//            if (i + nums[i] >= len - 1)
//            {
//                return true;
//            }
//            else
//            {
//                int l = i + nums[i];
//                for (int j = i + 1; j <= l; j++)
//                {
//                    l = max(l, j + nums[j]);
//                    if (l >= len - 1)
//                    {
//                        return true;
//                    }
//                }
//
//                if (l > i + nums[i])
//                {
//
//                    i = l - 1;
//                }
//                else
//                {
//                    if (nums[i + nums[i]] > 0)
//                    {
//                        i = i + nums[i] - 1;
//                    }
//                    else
//                    {
//                        return false;
//                    }
//                }
//            }
//        }
//
//
//
//        return true;
//    }
//};


//class Solution {
//public:
//    int jump(vector<int>& nums)
//    {
//        int len = nums.size();
//        int a[10010] = { 0 };
//        int right = 1;
//        for (int i = 0; i < len; i++)
//        {
//            for (int j = right; j <= i + nums[i] && j <= len - 1; j++)
//            {
//                a[j] = a[i] + 1;
//            }
//            right = max(right, i + nums[i] + 1);
//            if (right >= len)
//            {
//                break;
//            }
//        }
//
//        return a[len - 1];
//    }
//};



//#include <iostream>
//#include <string>
//using namespace std;
//
//int getday[] = { 0,31,29,31,30,31,30,31,31,30,31,30,31 };
//
//int main()
//{
//	int x, y;
//	cin >> x >> y;
//
//	int y1 = x / 10000;
//	int y2 = y / 10000;
//
//	int m2 = (y % 10000) / 100;
//	int d2 = y % 1000000;
//
//	int ret = 0;
//	for (int i = y1; i <= y2; i++)
//	{
//		int tmp = i;
//		int month = 0;
//		int day = 0;
//		while (tmp > 99)
//		{
//			month *= 10;
//			month += tmp % 10;
//			tmp /= 10;
//		}
//		while (tmp > 0)
//		{
//			day *= 10;
//			day += tmp % 10;
//			tmp /= 10;
//		}
//
//		int aaa = 0;
//		if ((month == 2) && ((i % 4 == 0 && i % 100 != 0) || (i % 400 == 0)))
//			aaa = 1;
//
//		if (i < y2 && month > 0 && month < 13 && day <= getday[month] + aaa)
//		{
//			ret++;
//		}
//		else if (i == y2 && month > 0 && month <= m2 && day <= d2)
//		{
//			ret++;
//		}
//	}
//	cout << ret << endl;
//	return 0;
//}


//#include <iostream>
//#include <algorithm>
//using namespace std;
//typedef long long ll;
//const int N = 1e5 + 10;
//
//int n, m;
//ll f[N] = { 0 };
//
//int main()
//{
//	cin >> n >> m;
//	ll x;
//	cin >> x;
//	for (int i = 1; i < m; i++)
//	{
//		ll y;
//		cin >> y;
//		int mini = min(x, y);
//		int maxi = max(x, y);
//
//		f[mini]++;
//		f[maxi]--;
//
//		x = y;
//	}
//
//	long long ret = 0;
//	for (int i = 1; i < n; i++)
//	{
//		f[i] = f[i] + f[i - 1];
//		ll a, b, c;
//		cin >> a >> b >> c;
//		ret += min(f[i] * a, f[i] * b + c);
//	}
//	cout << ret << endl;
//	return 0;
//}